package leecode.q144;


import java.util.*;

public class Solution {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    public List<Integer> pre(TreeNode root) {
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            list.add(pop.val);
            if (pop.right != null)
                stack.push(pop.right);
            if (pop.left != null)
                stack.push(pop.left);
        }
        return list;
    }

    public List<Integer> mid(TreeNode root) {
        if (root == null) {
            return list;
        }
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }

    public List<Integer> line(TreeNode root) {
        List<List<Integer>> rest = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null) {
                    queue.add(poll.left);
                } else {
                    System.out.println();
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                } else {
                    System.out.println();
                }
                size--;
            }
        }
        return list;
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 递归法
     */
    public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            // 左子树为null，右子树不为null，不对称
            return false;
        }
        if (left != null && right == null) {
            // 右子树为null，坐子树不为null，不对称
            return false;
        }
        if (left == null && right == null) {
            // 左右子树都为null，则返回true
            return true;
        }
        // 左右子树不为空，判断是否相等，不相等，则返回false
        if (left.val != right.val) {
            return false;
        }
        boolean inside = compare(left.left, right.right);
        boolean outside = compare(left.right, right.left);
        return inside && outside;
    }
}
